package com.hsc.offer.str;

/**
 * @author
 * @date 2025-06-07 剑指offer系列
 * @Description 1、在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
 */
public class SwordFingers1 {
    public static void main(String[] args) {
        // 创建一个二维数组
        int[][] array = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
        System.out.println("find(5,array) = " + find2(5, array));
    }

    /**
     * 笔试情况：快速写入
     * 传入一个目标数字，和一个二维数组，判断数组中是否有该数字
     *
     * @param target
     * @param array
     * @return
     */
    public static boolean find(int target, int[][] array) {
        // 边界条件判断
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }
        // 循环二维数组
        for (int i = 0; i < array.length; i++) {
            // 循环内层数组
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 面试情况：
     * 用最佳的方法完成题目。
     * <p>
     * 思路：
     * 每行的最后一个元素是这行最大的值。
     * 所以行数从0行开始，但是列数从最后一个开始比较。
     * 如果比当前这个最后一个值大，就必然大于这行的所有元素。就看下一行。
     * <p>
     * 如果没有当前的元素大，就查看左侧的元素。
     * <p>
     * 如果无法再向左了，或者无法再向下查找了。视为找不到这个元素。
     *
     * @param target
     * @param array
     * @return
     */
    public static boolean find2(int target, int[][] array) {
        // 定义二维数组的行 从第一行开始
        int row = 0;
        // 定义列 从每一行最后一列 开始比较
        int col = array[0].length - 1;

        while (true) {
            // 保证数组不越界 说明没找到
            if (row >= array.length || col < 0) {
                break;
            }
            // 如果当前的元素大于当前行的最后一个元素，就看下一行。
            if (target > array[row][col]) {
                // 看下一行 先判断行位置
                row++;
                // 进行下一次循环
                continue;
            }
            // 如果当前的元素小于当前行的最后一个元素，就看左侧的元素。
            if (target < array[row][col]) {
                // 寻找列的位置 如果没有，就返回false
                col--;
                // 进行下循环
                continue;
            }
            // 如果找到该元素了
            if (target == array[row][col]) {
                return true;
            }


        }
        return false;

    }

}
